package practice;

import java.util.*;

public class Day40 {
    //ruby和薯条
    private static int[] nums;
    private static long fun(int x) {
        //找出差值在[0,x]的对数
        long ret = 0l;
        int left = 0;
        int right = 0;
        while(right < nums.length) {
            while(nums[right] - nums[left] > x) {
                left++;
            }
            ret += (right-left+1);
            right++;;
        }
        return ret;
    }
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int l = in.nextInt();
        int r = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Arrays.sort(arr);
        nums = arr;
        System.out.println(fun(r) - fun(l-1));
    }

    //数学期望公式Cmn = n*(n-1)*(n-2)*...*(n-m+1) / m*(m-1)*(m-2)*..*1
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        double ret = 1.0;
        for(int i = n; i >= n-m+1; i--) {
            ret *= i;
        }
        for(int i = m; i >= 2; i--) {
            ret /= i;
        }
        //0.8表示中的概率
        for(int i = 0; i < m; i++) {
            ret *= 0.8;
        }
        //0.2表示不中的概率
        for(int i = 0; i < n-m; i++) {
            ret *= 0.2;
        }

        System.out.printf("%.4f",ret);
    }

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        fun(A.size(),A,B,C);
    }
    private void fun(int n, List<Integer> start,List<Integer> mid,List<Integer> end) {

        if(n == 1) {
            end.add(start.remove(start.size()-1));
            return;
        }
        //将n-1个盘子移动到第二根柱子上
        fun(n-1,start,end,mid);
        fun(1,start,mid,end);
        fun(n-1,mid,start,end);
    }

    public static void main(String[] args) {
        Day40 day40 = new Day40();
        List<Integer> A = new LinkedList<>();
        List<Integer> B = new LinkedList<>();
        List<Integer> C = new LinkedList<>();
        A.add(2);
        A.add(1);
        A.add(0);
        day40.hanota(A,B,C);
    }
    //汉诺塔进化（找规律，n=1，n=2，n=3......）
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long x = 1;
        long y = 2;
        long countB = 1;
        long countC = 2;
        for(int i = 2; i <= n; i++) {
            countB = (2 * y + 1) % 1000000007;
            countC = (2 * y + 2 + x) % 1000000007;
            x = countB;
            y = countC;
        }
        System.out.println(countB + " " + countC);
    }
    //ka和素因子
    private static int n;
    private static boolean[] flag = new boolean[1000];
    private static int sum;
    private static int ret = Integer.MAX_VALUE;
    public static void main4(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        n = len;
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        dfs(0,arr);
        System.out.println(ret == Integer.MAX_VALUE ? -1 : ret);
    }

    private static void dfs(int pos, int[] arr) {
        if(pos == n) {
            ret = Math.min(ret,sum);
            return;
        }
        //枚举arr[pos]里面所有的数，并判断是否是素因子
        for(int j = 2; j <= arr[pos]; j++) {
            if(arr[pos] % j == 0 && !flag[j] && isTrim(j)) {
                sum += j;
                flag[j] = true;
                dfs(pos+1,arr);
                flag[j] = false;
                sum -= j;
            }
        }
    }
    private static boolean isTrim(int j) {
        if(j <= 1) {
            return false;
        }
        for(int i = 2; i <= Math.sqrt(j); i++) {
            if(j % i == 0) {
                return false;
            }
        }
        return true;
    }
    //最小覆盖子串
    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        for (int i = 0; i < tLen; i++) {
            char ch = t.charAt(i);
            tMap.put(ch, tMap.getOrDefault(ch, 0) + 1);
        }
        int count = 0;
        int retI = -1;
        int retJ = -1;
        int left = 0;
        int right = 0;
        int min = Integer.MAX_VALUE;
        while (right < sLen) {
            sMap.put(s.charAt(right), sMap.getOrDefault(s.charAt(right), 0) + 1);
            if (sMap.getOrDefault(s.charAt(right), 0) <= tMap.getOrDefault(s.charAt(right), 0)) {
                count++;
            }

            while (count >= tLen) {
                if (right - left + 1 < min) {
                    min = right - left + 1;
                    retI = left;
                    retJ = right;
                }
                sMap.put(s.charAt(left), sMap.getOrDefault(s.charAt(left), 0) - 1);
                if (sMap.getOrDefault(s.charAt(left), 0) < tMap.getOrDefault(s.charAt(left), 0)) {
                    count--;
                }
                left++;
            }

            right++;
        }
        if(retI == -1 || retJ == -1) {
            return "";
        }
        return s.substring(retI, retJ + 1);
    }

    //最长非递减子序列
    public static void main5(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        int pos = 0;
        //其实就是找最长非递减子序列问题
        //第一个位置不用
        char[] arr = new char[n+1];
        for(int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if(pos == 0 || ch >= arr[pos]) {
                arr[++pos] = ch;
            }else {
                //使用二分找到最佳插入位置
                int left = 0;
                int right = pos;
                while(left < right) {
                    int mid = (right-left)/2+left;
                    if(arr[mid] <= ch) {
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                arr[left] = ch;
            }
        }
        System.out.println(n-pos);

    }
    //汉诺塔
    public static void main6(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long x = 1;
        long y = 2;
        for(int i = 2; i <= n; i++) {
            long a = (2 * y +1) % 1000000007;
            long b = (2 * y + x + 2) % 1000000007;
            x = a;
            y = b;
        }
        System.out.println(x + " " + y);


    }
    //图像翻转
    public void rotate(int[][] matrix) {
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < i; j++) {//遍历对角线下方的元素，然后翻转
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        //将[i][j]翻转到[j][i]位置
        //然后将[j][i]翻转到[j][n-i-1]位置
        int n = matrix.length;
        for(int[] arr : matrix) {
            for(int i = 0; i < n/2; i++) {
                //左半元素
                int tmp = arr[n-i-1];
                arr[n-i-1] = arr[i];
                arr[i] = tmp;
            }
        }
    }
    //接雨水
    public int trap(int[] height) {
        int n = height.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        for(int i = 1; i <= n; i++) {
            f[i] = Math.max(height[i-1],f[i-1]);
        }
        for(int i = n-1; i >= 0; i--) {
            g[i] = Math.max(height[i],g[i+1]);
        }
        int ret = 0;
        for(int i = 0; i < n; i++) {
            if(Math.min(g[i],f[i])-height[i] > 0) {
                ret += (Math.min(g[i],f[i])-height[i]);
            }
        }
        return ret;
    }
}
